1. Field of the Invention
This invention relates to the interactive generation and display of information, and more specifically to the interactive generation and display of tree structures.
2. Description of the Related Art
In recent times much effort has been devoted to the development and refinement of techniques for making decisions in complex environments. The arenas in which such decisions must be made are extremely diverse and can include the choice from a wide variety of options of personal investment vehicles, or the corporate selection of the optimum course of action in terms of the allocation of corporate resources. One mechanism which has found wide acceptance in the formulation of such decisions is the so called "decision tree".
Briefly, decision trees typically include a variety of nodes which take one of three forms. A node may be a decision node representing the need to make a choice between two or more possible courses of action. Alternatively, a node may be a chance node indicative of a point in the tree where one of two or more events will occur, but where the information about which event will actually occur is available only in terms of a probability. Finally a node may be an end node which represents the final point in a possible chain of decisions and random events.
The various nodes are connected by tree branches. Branches originating at a decision node each represent the selection of one of the several courses of action that are possible at the node. In many cases a particular choice will have a predictable economic effect. If the decision to be made for example is whether to add plant capacity or to add a third shift of factory workers, both the cost of expansion and the cost of adding employees can be predicted. It is common in tree structures to associate these costs with the particular branch to which they correspond.
Similarly, branches originating at chance nodes each represent one of the possible events that can occur at the node. In this case the probabilities that the decision maker thinks are appropriate for each of these events are associated with the corresponding branches.
Finally, each end node will have an associated economic effect. In the case of a profit maximization analysis, for example, this will represent the profit that is to be expected for a particular sequence of decisions and events that correspond to the path through the tree leading to the particular end node in question. Once the tree has been created, various statistical techniques can be used to evaluate the economic effects and the probabilities of the various paths through the tree and to select the optimum path from a statistical point of view. The value of the tree lies in the fact that it provides an ordered framework for assessing the impact on the final result of varying one or more of the a priori assumptions as to the probabilities at a chance node, or the a priori estimates of the various economic parameters.
More recently there have been attempts to provide a decision tree capability on various types of automatic data processing equipment. The computational capability of the machines coupled with convenient display capability, such as by means of a cathode ray tube (CRT), can result in a flexible means for decision tree analysis. One problem in this regard, however, stems from the size of most practical decision tree structures. If the tree is to be displayed on paper this does not create major problems. If the tree, however, is to be displayed on the limited dimensions of a CRT, a tradeoff must be made between the desire to display the entire tree to provide perspective, and the need to display local parts of the tree with sufficient size to be readily interpretable by the operator. In the past, attempts have been made to resolve this problem by displaying a magnified version of a local portion of the tree. An example of this is the Harvard Project Manager which is available from Harvard Software Inc., 521 Great Road, Littleton Road, Mass. This approach may not always provide a desirable result since decision trees tend to be expanding structures with a very thin branch density near the base of the tree and a dense branch structure at the top or end. Accordingly, a display magnification which is appropriate for one portion of the tree may not provide sufficient information at other portions of the tree. This same difficulty may be encountered in other tree structures such as PERT charts and knowledge representations in the case of expert systems.